import { Comparator, CompareFunction } from "../utils/Comparator";
import { IndexOutOfBoundsError } from "../utils/Error";
import { Heap } from "./heap.interface";

/**
 * 二叉推——最大堆
 */
export class BinaryHeap<T> implements Heap<T> {

    public elems: T[] = [];
    private _size: number = 0;
    private comparator: Comparator<T>;

    constructor(elements?: T[], comparaFunc?: CompareFunction<T>);
    constructor(compareFunc?: CompareFunction<T>);

    constructor(elemsOrComparaFn?: CompareFunction<T> | T[], comparaFunc?: CompareFunction<T>) {
        // js 的数组自动扩容，实现不考虑扩容
        if (elemsOrComparaFn) {
            if (Array.isArray(elemsOrComparaFn)) {
                this.elems = [...elemsOrComparaFn];
                this._size = this.elems.length;
                this.comparator = new Comparator(comparaFunc);
                this.heapify();
            } else {
                this.comparator = new Comparator(elemsOrComparaFn);
            }
        } else {
            // 自定义比较函数
            this.comparator = new Comparator(elemsOrComparaFn);
        }
    }

    get(): T {
        this.emptyCheck();
        return this.elems[0];
    }

    add(elem: T): void {
        this.elems[this._size]= elem;
        this._size++;
        this.siftUp(this._size-1);
    }
    remove(): T {
        const top = this.get();
        this._size--;
        if (this._size === 0) return top;

        this.elems[0] = this.elems.pop()!;
        this.siftDown(0);
        return top;
    }
    replace(elem: T): T|null {
        const oldTop = this._size === 0 ? null : this.elems[0];
        if (this._size === 0) {
            this.elems[0] = elem;
            this._size++;
        } else {
            this.elems[0] = elem;
            this.siftDown(0);
        }
        return oldTop;
    }
    size(): number {
        return this._size;
    }
    isEmpty(): boolean {
        return this._size === 0;
    }
    clear(): void {
        this.elems = [];
        this._size = 0;
    }

    /** 批量建堆 */
    heapify () {
        // 自上而下的上滤
        // for (let i = 1; i < this._size; i++) {
        //     this.siftUp(i);
        // }

        // 自下而上的下滤 效率更高一些
        for (let i = ((this._size >> 1)-1); i>=0; i--) {
            // 从最后一个非叶子节点开始下滤
            this.siftDown(i);
        }
    }

    /** 从索引 index 处上滤 */
    private siftUp (index: number) {
        let curElem = this.elems[index];
        while(index > 0) {
            const parentIdx = this.getParentIndex(index)!;
            const parent = this.elems[parentIdx];
            if (this.comparator.lessThan(parent, curElem)) {
                this.elems[index] = parent;
                index = parentIdx;
            } else {
                break;
            }
        }
        this.elems[index] = curElem;
    }

    /** 从索引 index 处下滤 */
    private siftDown (index: number) {

        while (index < this._size) {
            const leftIdx = this.getLeftChildIndex(index);
            const rightIdx = this.getRightChildIndex(index);

            if (rightIdx !== null) {    // 有两个子节点
                if (
                    this.comparator.lessThan(this.elems[index], this.elems[leftIdx!])
                    &&
                    this.comparator.lessThan(this.elems[index], this.elems[rightIdx!])
                ) {
                    if (this.comparator.greaterThan(this.elems[leftIdx!], this.elems[rightIdx])) {
                        this.swap(index, leftIdx!);
                        index = leftIdx!;
                    } else {
                        this.swap(index, rightIdx);
                        index = rightIdx;
                    }
                } else if (this.comparator.lessThan(this.elems[index], this.elems[leftIdx!])) {
                    this.swap(index, leftIdx!);
                    index = leftIdx!;
                } else if (this.comparator.lessThan(this.elems[index], this.elems[rightIdx!])) {
                    this.swap(index, rightIdx);
                    index = rightIdx;
                } else {
                    return;
                }

            } else if (leftIdx !== null && this.comparator.lessThan(this.elems[index], this.elems[leftIdx])) {  // 只有 左子节点
                const temp =  this.elems[index];
                this.elems[index] = this.elems[leftIdx];
                this.elems[leftIdx] = temp;
                index = leftIdx;
            } else {    // 没有子节点
                return;
            }
        }
    }

    private swap (idx1: number, idx2: number) {
        const temp = this.elems[idx1];
        this.elems[idx1] = this.elems[idx2];
        this.elems[idx2] = temp
    }

    private getParent(index: number): T|null {
        const parentIdx = this.getParentIndex(index);
        if (parentIdx === null) return null;
        return this.elems[parentIdx];
    }

    private getLeftChild (index: number): T|null {
        const leftIdx = this.getLeftChildIndex(index);
        if (leftIdx === null) return null;
        return this.elems[leftIdx];
    }
    private getRightChild (index: number): T|null {
        const rightIdx = this.getRightChildIndex(index);
        if (rightIdx === null) return null;
        return this.elems[rightIdx];
    }

    private getParentIndex (index: number): number|null {
        if (index === 0) return null;
        return  (index - 1)>>1;
    }
    private getLeftChildIndex (index: number): number|null {
        let leftIdx = 2 * index + 1;
        if (leftIdx > this._size-1) return null;
        return leftIdx;
    }
    private getRightChildIndex (index: number): number|null {
        let rightIdx = 2 * index + 2;
        if (rightIdx > this._size-1) return null;
        return rightIdx;
    }

    /** 空检测 */
    private emptyCheck () {
        if (this._size === 0) {
            throw new IndexOutOfBoundsError('BinaryHead index is out of bound.');
        }
    }
}